package com.itcast.demo.simple;

/**
 * 从0,1,2,...,n这n+1个数中选择n个数，组成有序数组，请找出缺失的那个数，要求O(n)尽可能小。
 *
 * @author zheng.zhang
 */
public class Test7 {
    public static void main(String[] args) {
        Test7 test7 = new Test7();
        int[] arr = {0, 1, 2, 3, 4, 5, 7};
        int solve = test7.solve2(arr);
        System.out.println(solve);
    }

    /**
     * 找缺失数字
     *
     * @param a int整型一维数组 给定的数字串([0,1,2,3,4,5,7])
     * @return int整型(6)
     */
    public int solve(int[] a) {
        if (a == null) {
            return -1;
        }
        int n = a.length;
        for (int i = 0; i < a.length; i++) {
            n ^= a[i] ^ i;
        }
        return n;
    }

    /**
     * 找缺失数字二分法
     *
     * @param a 数组
     * @return 缺失数字
     */
    public int solve2(int[] a) {
        if (a == null) {
            return -1;
        }
        int start = 0;
        int end = a.length - 1;
        while (start < end) {
            int middle = (start + end) / 2;
            if (a[middle] == middle) {
                start = middle + 1;
            } else if (a[middle] > middle) {
                end = middle;
            }
        }
        return start;
    }
}
